package org.labuladong.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-2:27
 * @Description:
 *
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
 * 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
 * 示例 1：
 *
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 * 示例 2：
 *
 * 输入: s1= "ab" s2 = "eidboaoo"
 * 输出: False
 * 提示：
 *
 * 1 <= s1.length, s2.length <= 104
 * s1 和 s2 仅包含小写字母
 * @version: 1.0
 */
public class LCR_014_字符串的排列 {
	public boolean checkInclusion(String t, String s) {
		// 初始化需要的字符和窗口中的字符的哈希表
		Map<Character, Integer> need = new HashMap<>();
		Map<Character, Integer> window = new HashMap<>();
		for (char c : t.toCharArray()) {
			need.put(c, need.getOrDefault(c, 0) + 1);
		}

		int left = 0, right = 0;
		int valid = 0; // 窗口中满足条件的字符数量
//		int start = 0; // 最小覆盖子串的起始索引
//		int len = Integer.MAX_VALUE; // 最小覆盖子串的长度

		while (right < s.length()) {
			// 将移入窗口的字符c加入窗口
			char c = s.charAt(right);
			right++;

			// 如果c是t中的字符，则更新窗口计数
			if (need.containsKey(c)) {
				window.put(c, window.getOrDefault(c, 0) + 1);
				if (window.get(c).equals(need.get(c))) {
					valid++;
				}
			}

			// 判断左侧窗口是否要收缩
//			while (valid == need.size()) {
			while (right - left >= t.length()) {
				// 在这里更新最小覆盖子串
//				if (right - left < len) {
//					start = left;
//					len = right - left;
//				}
				if(valid == need.size())
						return true;
				// d 是将移出窗口的字符
				char d = s.charAt(left);
				left++;

				// 进行窗口内数据的一系列更新
				if (need.containsKey(d)) {
					if (window.get(d).intValue() == (need.get(d).intValue())) {
						valid--;
					}
					window.put(d, window.get(d) - 1);
				}
			}
		}

	// 没找到
		return false;
	}
}
